#include<cstdio>
#include<algorithm>
#include<string>
#include<vector>

using namespace std;

string text = string("abcaabcabca");
string pattern = string("abc");
int n, m;
vector<int> pi;     // prefix function.
vector<int> answers; // matching positions.
int main(){
    printf("Text: %s\n", text.c_str());
    printf("Pttern: %s\n", pattern.c_str());
    n = text.size();
    m = pattern.size();

    // Compute prefix function
    pi.push_back(-1);
    int k = -1;
    for(int i = 1; i < m;i++){
        while(k > -1 && pattern[k+1] != pattern[i]){
            k = pi[k];
        }
        if (pattern[k+1] == pattern[i]) {
            k = k+1;
        }
        pi.push_back(k);
    }

    // Match
    k = -1;
    for(int i = 0; i < n;i++){
        while ( k > -1 && pattern[k+1] != text[i]) {
            k = pi[k];
        }
        if (pattern[k+1] == text[i]) {
            k = k+1;
        }
        if (k == m-1) {
            answers.push_back(i-m+1);
            k = pi[k];
        }
    }
    printf("Matching indices(from 0): ");
    for(int i = 0; i < answers.size(); i++){
        printf("%d ", answers[i]);
    }
    printf("\n");
    return 0;
}
